We design an expected polynomial-time, truthful-in-expectation,(1-1/e)-approximation mechanism for welfare maximization in a fundamental classof combinatorial auctions. Our results apply to bidders with valuations thatare m matroid rank sums (MRS), which encompass most concrete examples ofsubmodular functions studied in this context, including coverage functions,matroid weighted-rank functions, and convex combinations thereof. Ourapproximation factor is the best possible, even for known and explicitly givencoverage valuations, assuming P != NP. Ours is the firsttruthful-in-expectation and polynomial-time mechanism to achieve aconstant-factor approximation for an NP-hard welfare maximization problem incombinatorial auctions with heterogeneous goods and restricted valuations. Our mechanism is an instantiation of a new framework for designingapproximation mechanisms based on randomized rounding algorithms. A typicalsuch algorithm first optimizes over a fractional relaxation of the originalproblem, and then randomly rounds the fractional solution to an integral one.With rare exceptions, such algorithms cannot be converted into truthfulmechanisms. The high-level idea of our mechanism design framework is tooptimize directly over the (random) output of the rounding algorithm, ratherthan over the input to the rounding algorithm. This approach leads totruthful-in-expectation mechanisms, and these mechanisms can be implementedefficiently when the corresponding objective function is concave. For bidderswith MRS valuations, we give a novel randomized rounding algorithm that leadsto both a concave objective function and a (1-1/e)-approximation of the optimalwelfare.
展开▼
